
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1714. -- [Usaco2007 China]Treasure -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1714: [Usaco2007 China]Treasure</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>3&nbsp;&nbsp;<span class=green>Solved: </span>1<br>[<a href='submitpage.php?id=1714'>Submit</a>][<a href='problemstatus.php?id=1714'>Status</a>][<a href='bbs.php?id=1714'>Discuss</a>]</center><h2>Description</h2><div class=content>
Canmuu and his friends have recently acquired a large cache of
plutonium and have agreed to bury their newfound treasure at some
road intersection deep in the Canadian wilderness. Any sort of treasure
burial calls for a treasure map so they've decided to create one
of their own.

The road network consists of N (4 <= N <= 100,000) intersections
(conveniently numbered 1..N) with N roads connecting them. As busy
intersections confuse everybody, every intersection has at least
one road that leads to it, and no intersection has more than four
roads connected to it. Excellent maintenance has ensured that a
moose can always run either way between any pair of intersections.
Furthermore, Canmuu has decided the plutonium should not be buried
at any of the 4-way intersections since busy traffic decreases the
secrecy of the buried treasure.

The treasure map will contain all the roads and all the intersections.
But, to conceal the treasure's location, only one road intersection
on the treasure map is to be labeled: the intersection at which the
treasure is buried (which has a big red 'X', of course).

Ever the alert moose, Canmuu drew some trial maps to see what they
would look like depending on where the treasure was buried. Canmuu
noticed that the moose might draw similar maps even if they bury
their treasure in two different locations. Their curiosity piqued,
the herd began trying to figure out how many distinct maps they
could end up making.

Maps are indistinct if it is possible to assign a mapping such that:

  * the X-labeled intersections on both maps correspond,

  * a correspondence can be created for the other intersections,
    such that

  * when the well-chosen intersection correspondence is determined,
    the roads that connect the intersections also correspond.

By way of example, consider the maps below where N = 4; the treasure
might be buried at any of four intersections:

        +             +             X           +
       /|            /|            /|          /|
  X---+ |       +---X |       +---+ |     +---+ |
       \|            \|            \|          \|
        +             +             +           X

The final two maps, however, are not distinct since one can create
a correspondence for the vertices (consider the map upside down)
and then the roads correspond exactly. Thus, only three maps are
distinct.

How many distinct maps are possible for a given set of roads?

</div><h2>Input</h2><div class=content>* Line 1: A single integer: N

* Lines 2..N + 1: Two space-separated integers: A and B (1 <= A <= N;
        1 <= B <= N), indicating that there is a road connecting
        intersections A and B

</div><h2>Output</h2><div class=content>
* Line 1: A single integer that is the number of distinct treasure
        maps
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
4<br />
1 2<br />
2 3<br />
3 1<br />
1 4<br />
<br />
INPUT DETAILS:<br />
<br />
Here is a drawing of the roads and the intersections.<br />
<br />
                   4---1---2<br />
                        \ /<br />
                         3<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
3<br />
<br />
OUTPUT DETAILS:<br />
<br />
The treasure can be buried at any intersection. However, burying it at<br />
intersections 2 and 3 yields maps that are identical to each other. So the<br />
total number of distinct treasure maps is 3.<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1714'>Submit</a>][<a href='problemstatus.php?id=1714'>Status</a>][<a href='bbs.php?id=1714'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
